#include <bits/stdc++.h>
using namespace std;

/*
2962. 统计最大元素出现至少 K 次的子数组
已解答
中等
相关标签
相关企业
给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

 

示例 1：

输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
示例 2：

输入：nums = [1,4,2,1], k = 3
输出：0
解释：没有子数组包含元素 4 至少 3 次。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= k <= 105
*/

// 法一
/**
 * max_element(_ForwardIterator __first, _ForwardIterator __last)
 * @brief 返回范围 [__first, __last) 中的最大元素的迭代器。
 * 
 * 该函数会在指定范围内查找最大值，并返回指向该最大值的迭代器。
 * 如果范围为空，则返回 __last。
 * 
 * @tparam _ForwardIterator 可用于遍历范围的前向迭代器类型。
 * @param __first 范围的起始迭代器。
 * @param __last 范围的结束迭代器（不包含在范围内）。
 * @return _ForwardIterator 指向范围内最大元素的迭代器。
 */
class Solution {
	public:
	using ll = long long;
	long long countSubarrays(vector<int>& nums, int k) {
		int max_val = *max_element(nums.begin(), nums.end());
		int left = 0, cnt = 0;
		ll ans = 0;

		for (int right = 0; right < nums.size(); ++right) {
			if (nums[right] == max_val) {
				cnt++;
			}
			// 窗口收缩
			while (cnt >= k) {
				if (nums[left] == max_val) {
					cnt--;
				}
				// 左指针要过来达成收缩效果
				left++;
			}
			// 累加当前 left 的位置（即有效左边界的数量）
			ans += left;
		}
		return ans;
	}
};

// 法二
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, int k) {
		// 找到数组中的最大值
		// C++20 标准
		int mx = ranges::max(nums);
		long long ans = 0;
		int cnt_mx = 0; // 当前窗口内最大值出现的次数
		int left = 0;   // 滑动窗口左边界
		// 滑动窗口遍历所有右边界
		for (int x : nums) {
			// 更新当前窗口的最大值计数
			cnt_mx += (x == mx);
			// 当窗口内最大值出现次数等于k时，开始收缩左边界
			// 直到最大值出现次数不足k次（刚好变成k-1次）
			while (cnt_mx == k) {
				cnt_mx -= (nums[left] == mx); // 左移时更新计数器
				left++;                       // 移动左边界
			}
			// 此时left的位置是第一个不满足条件的左边界
			// 所有[0, left-1]的位置作为左边界都满足条件
			// 累计有效子数组数量（即有多少个左边界可选）
			ans += left;
		}
		return ans;
	}
};

// 法三
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, int k) {
		// 获取数组中的最大值
		int max_val = *max_element(nums.begin(), nums.end());
		int count = 0;        // 记录当前窗口内最大值出现的次数
		long long result = 0; // 最终结果
		
		// 双指针维护滑动窗口：[left, right) 区间
		for (int left = 0, right = 0; left < nums.size(); left++) {
			// 扩展右边界，直到窗口内最大值出现次数 >=k 或 right越界
			while (right < nums.size() && count < k) {
				if (nums[right] == max_val) {
					count++; // 遇到最大值时增加计数
				}
				right++;     // 右移指针
			}
			// 如果当前窗口满足条件（count >=k），累加符合条件的子数组数量
			// 此时所有以 left 为左端点，右端点在 [right-1, nums.size()-1] 的区间都满足条件
			// 因此有效子数组数量为 nums.size() - (right-1) = nums.size() - right + 1
			if (count >= k) {
				result += nums.size() - right + 1;
			}            
			// 左边界右移前，若当前左边界元素是最大值，减少计数器
			if (nums[left] == max_val) {
				count--;
			}
		}
		return result;
	}
};